package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-04-08 09:00
 */
public class BO429N叉数的层次遍历 {

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node1 = new Node(3);
        Node node2 = new Node(2);
        Node node3 = new Node(4);
        Node node4 = new Node(5);
        Node node5 = new Node(6);

        List<Node> nodes = new ArrayList<>();
        nodes.add(node4);
        nodes.add(node5);
        node1.children = nodes;
        List<Node> nodes2 = new ArrayList<>();
        nodes2.add(node1);
        nodes2.add(node2);
        nodes2.add(node3);
        node.children = nodes2;

        System.out.println(levelOrder2(node));
    }

    /**
     * 层次遍历 使用队列存储下一集节点   先进先出
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(Node root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> lists = new ArrayList<>();
        Queue<Node> queueOne = new LinkedList();
        Queue<Node> queueTwo = new LinkedList();
        queueOne.add(root);
        List<Integer> list = new ArrayList<>();
        while (!queueOne.isEmpty()) {
            Node node = queueOne.poll();
            list.add(node.val);
            if (node.children != null) {
                for (Node nodeSon : node.children) {
                    queueTwo.add(nodeSon);
                }
            }
            if (queueOne.isEmpty()) {
                lists.add(list);
                list = new ArrayList<>();
                while (!queueTwo.isEmpty()) {
                    queueOne.add(queueTwo.poll());
                }
            }
        }
        return lists;
    }

    /**
     * 层次遍历 使用队列存储下一集节点   先进先出
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder2(Node root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> lists = new ArrayList<>();
        Queue<Node> queueOne = new LinkedList();
        queueOne.add(root);
        queueOne.add(null);
        List<Integer> list = new ArrayList<>();
        while (!queueOne.isEmpty()) {
            Node node = queueOne.poll();
            if (node == null) {
                lists.add(list);
                if(queueOne.isEmpty()){
                    break;
                }
                list = new ArrayList<>();
                queueOne.add(null);
                continue;
            }
            list.add(node.val);
            if (node.children != null) {
                for (Node nodeSon : node.children) {
                    queueOne.add(nodeSon);
                }
            }
        }
        return lists;
    }


    static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    ;
}
